The present invention relates to the field of system caching. Specifically, the present invention provides a system and method for coordinated hierarchical caching in a client/server environment, particularly on the World Wide Web. Furthermore, the present invention provides a cache replacement method which adapts to changing system resource bottlenecks.
Glossary of Terms
While dictionary meanings are also implied by terms used here, the following glossary of some terms may be useful.
Client
A client is a computer which typically issues commands to one or more servers which perform the task associated with the command.
Server
Any computer that performs a task at the command of one or more computers is a server. A Web server typically supports one or more clients.
World Wide Web (Web)
The Internet""s application that lets people seeking information on the Internet switch from server to server and database to database. Users can click on highlighted words or phrases of interest (hyperlinks), click on graphics such as applets or image maps, fill in forms, and enter URLs. An Internet Web server supports clients and provides information. The Web can be considered as the Internet with all of the resources addressed as URLs and which uses HTTP protocols to transfer information between computers and which uses HTML (among other formats) to display the information corresponding to URLs and provide a point-and-click interface to other URLs.
Universal Resource Locator (URL)
A way to identify or address information on the Internet.
HyperText Markup Language (HTML)
HTML is a standard device-independent representation of content on Web servers. Web servers may deliver content (including hyperlinks) to clients in HTML with confidence that the client will choose an appropriate presentation.
Hypertext Transfer Protocol (HTTP)
HTTP is an example of a stateless protocol, which means that every request from a client to a server is treated independently. Clients send request to servers and servers respond using this protocol.
Internet Browser or Web Browser
A graphical interface tool that runs Internet protocols such as HITP, and displays results on the customer""s screen. The browser can act as an Internet tour guide, complete with pictorial desktops, directories and search tools used when a user xe2x80x9csurfsxe2x80x9d the Internet. In this application, the Web browser is a client service which communicates with the Web servers.
Object
An object is data which can be stored in a cache.
Cache Replacement Policy
A cache replacement policy is an algorithm for determining which objects should be placed in a cache when the cache contains insufficient space to contain all objects.
Caching is commonly used for improving performance on computer systems. By caching an object, the cost for fetching or creating the object is only incurred once. Subsequent requests for a cached object can be satisfied from the cache, a process which incurs significantly less overhead than regenerating the object or fetching it from a remote location.
Systems on the World Wide Web (xe2x80x9cWebxe2x80x9d) today often contain browser and proxy caching (see xe2x80x9cCaching Proxies: Limitations and Potentialsxe2x80x9d by M. Abrams et. al., xe2x80x9cFourth International World Wide Web Conference Proceedings,xe2x80x9d December 1996, pp. 119-133 and xe2x80x9cWorld Wide Web Proxiesxe2x80x9d by A. Luotonen and K. Altis in xe2x80x9cComputer Networks and ISDN Systems,xe2x80x9d vol. 27 (1994), pp. 147-154) to improve performance. While these caching systems are sometimes hierarchical in nature, normally caching at one level is not coordinated with caching at the next level. In other words, each cache makes decisions independently of what another cache is doing.
In U.S. patent application Ser. No. 08/831,237 entitled xe2x80x9cCollaborative Cachingxe2x80x9d by Yu et al., filed Apr. 2, 1997, a method for collaborative caching in a hierarchy of proxy caches is disclosed. The disclosed system bases a client""s or proxy""s caching decision on whether the object is cached at another proxy location in the hierarchy closer to the Web server which stores or generates the object. No cache is disclosed to be local to the Web server and the client or proxy must rely on header information contained in the object and caching status information provided by the other proxy location for its caching decision. While this system addresses general network access (browsing) speed, it does not address the problem of slow service of Web pages (such as dynamic pages) to clients from a particularly hot Web server site. The Yu system would have to be implemented across the internet""s multitude of proxy servers to provide improved service from a particular Web site. Finally, it would be practically impossible to update, with the Yu system, dynamic pages (those generated xe2x80x9con the flyxe2x80x9d) in view of network bottlenecks and the decoupled nature of the proxies to the Web server. Thus, there is a need for a client/server system that implements a true hierarchy of caches from a Web server level to the client browser level, supports dynamic pages and coordinates the actions of the caches so that superior performance can be attained.
Level 1, level 2, etc. caches in uniprocessors are well known to those skilled in the art. However, while level 1 and level 2 processor caches are often coordinated to some extent (for example, the decision to place an object in one processor cache might be made depending on whether the object is contained in another processor cache), the client/server environment has characteristics which pose different problems to a caching system. First, in the client/server environment, there can be multiple level 2 (server) caches located behind a level 1 (e.g., router) cache, all with different contents. In contrast, a uniprocessor contains, at most, one level 2 cache. Second, compared with processor caches, there are more constraints over what can be stored in these router and server caches. For example, in a Web-based client/server environment, it may be necessary to keep some URLs out of a router cache in order to force a particular request to be directed to a server. It is also undesirable to cache objects (e.g., static pages) in server caches which are inexpensive for the Web server to generate. This would not be the case for processor caches because level 2 caches are generally faster than main memory. Third, the parameters affecting admittance to the cache and cache replacement are significantly different for the two environments. In processor caching, least recently used (LRU) information generally suffices. In Web-based client/server systems, considerations such as the expected number of accesses per unit time, expected lifetime, object size and time to create or fetch the object are important to consider.
Another prior art system is the Parallel-Sysplex in the System 390 (Special Issue on S/390 Parallel Sysplex Cluster, IBM Systems Journal, Vol. 36, No. 2, 1997). The Parallel Sysplex has level 1 database caches in each of the processing nodes and a level 2 cache in the coupling facility, which is shared among the nodes. While the level 1 and level 2 caches in the Sysplex are coordinated, there are several differences between the Sysplex and a client/server system.
In the Sysplex, the database system runs at the same node as the level 1 cache, the level 2 cache is on a shared coupling facility and the permanent data is located on shared disks accessed from the node at which the level 1 caches reside. In a client/server system, however, remote clients may have to make requests which initially go to the level 1 cache, while the permanent locations of the data are at the nodes at which the level 2 caches reside. Furthermore, the criteria for placing objects in the level 1 or level 2 caches are very different for the two systems. In the Sysplex, hot shared records/objects, especially those frequently updated, are placed in the level 2 coupling facility cache. In the client/server case, there is no concept of sharing (i.e. programs at different Sysplex nodes that access and update the same object), and the criteria for caching objects should include the size of the objects, the hotness (desirability measured by hits) of the objects, the time to create or fetch the objects, and the update rate. Therefore, there is a need for a coordinated hierarchical caching system directed to the client/server environment where a level 2 cache is located where the objects are permanently stored or generated.
In many cases, caches do not have sufficient memory to store all cacheable objects at one time. Selectivity must be applied in determining which objects should be cached when the cache is full or almost full. To address this problem, a number of cache replacement algorithms exist in the prior art such as that disclosed in U.S. patent application Ser. No. 08/958,506 entitled xe2x80x9cA New Algorithm for Cache Replacementxe2x80x9d by Challenger et al., filed Oct. 27, 1997 and herein incorporated by reference. These algorithms, however, have been designed to address the problem of a single system bottleneck such as a system processor. Networked systems generally may suffer from at least one of several potential bottlenecks at any given time. In addition, the bottleneck(s) having the dominant impact on performance may change over time.
Therefore, there is a need for an algorithm that can handle situations where one of several resources (e.g., server CPU, router CPU, network bandwidth) might create bottlenecks and where the resource which is causing the bottleneck (if any) may change dynamically.
The present invention provides a system for hierarchically caching objects including one or more level 1 nodes, each including at least one level 1 cache; one or more level 2 nodes within which the objects are permanently stored or generated upon request, each level 2 node coupled to at least one of the one or more level 1 nodes and including one or more level 2 caches; and storing device for storing, in a coordinated manner, one or more objects in at least one level 1 cache and/or at least one level 2 cache, based on a set of one or more criteria.
The set of one or more criteria preferably include at least one of: a size of one or more of the objects, a storage space available in one or more of the caches, a CPU load on one or more of the level 1 nodes, a CPU load on one or more of the level 2 nodes, a pattern of data accesses to one or more of the objects, a frequency of update of one or more of the objects, a time to create or fetch one or more of the objects, and network traffic between one or more of the level 1 nodes and one or more of the level 2 nodes.
The level 1 nodes can be Web server accelerators, routers or Web servers. The nodes are preferably disposed within an encapsulated cluster.
The system of the present invention can include one or more level 3 nodes coupled to at least one of the one or more level 2 nodes and wherein the storing device comprises a device for storing one or more objects in at least one level 3 cache and/or at least one of the at least one level 1 cache, the at least one level 2 cache and the at least one level 3 cache.
Finally, the present invention also provides a system for hierarchically caching objects including one or more level I nodes, each including at least one level I cache, for all integers I such that L greater than =I greater than 0 where L greater than =3, wherein the objects are permanently stored or generated on at least one of the nodes; and a storing device for storing, in a coordinated manner, one or more of the objects in at least one level j cache and/or at least one level k cache where L greater than =k greater than j greater than 0, based on a set of one or more criteria.
The present invention also provides a method for caching objects including the steps of: providing one or more level 1 nodes, each including at least one level 1 cache; providing one or more level 2 nodes within which the objects are permanently stored or generated upon request, each level 2 node coupled to at least one of the one or more level 1 nodes and including one or more level 2 caches; and storing one or more objects in at least one level 1 cache and/or at least one level 2 cache, in a coordinated manner based on a set of one or more criteria.
Preferably, the set of one or more criteria includes at least one of: a size of one or more of the objects, a storage space available in one or more of the caches, a CPU load on one or more of the level 1 nodes, a CPU load on one or more of the level 2 nodes, a pattern of data accesses to one or more of the objects, a frequency of update of one or more of the objects, a time to create or fetch one or more of the objects, and network traffic between one or more of the level 1 nodes and one or more of the level 2 nodes.
The storing step preferably includes the step of maintaining information that one or more objects should not be cached in at least one level 1 cache.
The method of the present invention preferably further includes the steps of: receiving, at the one or more level 1 nodes, a request for an object from a client; determining whether the requested object is in the at least one level 1 cache; transmitting, in response to the object being found in the at least one level 1 cache, the object from the at least one level 1 cache to the client; and attempting, in response to the object not being found in the at least one level 1 cache, to satisfy the request from the at least one level 2 cache. The attempting step preferably includes the steps of: forwarding the object to at least one of the one or more level 2 nodes; determining whether the object is in at least one level 2 cache corresponding to the at least one of the one or more level 2 nodes; and sending, in response to the object being found in the at least one level 2 cache, the object from the level 2 cache to the client. Preferably, the method further includes the steps of identifying the object as being sufficiently hot; and moving the object or a copy of the object to a level 1 cache.
Preferably, at any specific time, an object is stored in, at most, one of the level 2 caches.
The method of the present invention preferably further includes the step of preventing the caching of an object in a level 2 cache where a cost of providing the object from the level 2 cache is high relative to a cost of providing the object from a level 2 node corresponding to the level 2 cache. The cost of providing the object from the level 2 cache preferably includes a cost of at least one invalidation and updating of the object in the cache after its value changes.
The method of the present invention preferably further includes the step of caching, in response to a level 1 cache being full, an object in a level 2 cache.
The method of the present invention preferably further includes the step of preventing an object from being cached in a level 1 cache. It is also preferable that the method further includes the step of allowing the object to be cached in at least one level 2 cache. The preventing step is made necessary due to a difficulty of maintaining sufficiently current values of the object in the level 1 cache or because the request for the object causes a side effect on a level 2 node.
The storing step preferably includes the step of determining the object to be a general cache candidate. The determining step can include the step of checking a text string or header information associated with the object, the step of applying a function to the object (such as determining the size of the object or determining the expected lifetime of the object).
The storing step preferably includes the step of identifying the object to be a level 1 cache candidate. The identifying step can include the step of determining the size of the object, determining any limits in logging facilities of the associated level 1 node or determining sufficient space in the level 1 cache.
The storing step preferably includes the step of identifying the object to be a level 2 cache candidate. The identifying step can include the step of determining the object not to be a level 1 cache candidate, the step of determining the size of the object, or the step of determining sufficient space in the level 2 cache.
The storing step preferably includes the step of applying a cache replacement policy. The applying step can include the steps of applying, for part of the at least one level 1 cache, a cache replacement policy designed to minimize utilization of a set of one or more resources in the system; and using, for other parts of the at least one level 1 cache, one or more other cache replacement policies designed to minimize utilization of one or more other sets of one or more resources in the system.
The present invention also provides a method for caching objects comprising the steps of: providing one or more level I nodes, each including at least one level I cache, where L greater than =3 and I is an integer such that L greater than =I greater than 0, wherein the objects are permanently stored or generated on at least one of the nodes; and storing, in a coordinated manner, one or more objects in at least one level j cache and/or at least one level k cache where L greater than =k greater than j greater than 0, based on a set of one or more criteria. The set of one or more criteria preferably includes at least one of: a size of one or more of the objects, a storage space available in one or more of the caches, a CPU load on one or more of the level I nodes, a pattern of data accesses to one or more of the objects, a frequency of update of one or more of the objects, a time to create or fetch one or more of the objects, and network traffic between one or more of the level I nodes, the level j nodes and/or the level k nodes.
Another aspect of the present invention is the novel cache replacement method used by the Web server accelerator (e.g., router). This method for determining which objects should be placed in a cache is particularly useful when multiple parameters affecting the desirability of caching objects are non-uniform across objects. Such parameters include the frequency with which an object is accessed, object size, the time to calculate an object or fetch it from a remote location, and the lifetime (i.e. time between updates) of an object.
Using the method of the present invention, a router applies a combination of three cache replacement algorithms to manage different parts of its cache. One replacement algorithm is designed for optimal performance when server CPUs are the bottleneck. Another replacement algorithm is designed for optimal performance when the router CPU is the bottleneck. The third algorithm is designed for optimal performance when the network between the router and the server(s) is the bottleneck. When one of the three aforementioned resources becomes a bottleneck, the router increases the amount of cache storage space managed by the replacement algorithm designed to minimize consumption of the bottleneck resource. Another technique of the present invention which is sometimes used to improve performance when a resource becomes a bottleneck is to vary the percentage of requests which bypass the router""s cache and are sent directly to a server.
Particularly, the present invention provides, in a system adapted to receive requests for objects from one or more clients, the system having a set of one or more level 1 nodes, each containing at least one level 1 cache, a method for managing a level 1 cache including the steps of: applying, for part of the at least one level 1 cache, a cache replacement policy designed to minimize utilization of a set of one or more resources in the system; and using, for other parts of the at least one level 1 cache, one or more other cache replacement policies designed to minimize utilization of one or more other sets of one or more resources in the system.
The cache replacement policy is preferably designed to minimize resources on a level 1 node containing the level 1 cache. Here, the cache replacement policy can estimate a desirability of caching an object from an expected number of hits to the object per unit time if the object is cached divided by a size of the object. Preferably, the cache replacement policy estimates the desirability of caching the object by calculating or estimating the quantity (1/axe2x88x92p/u)/s, where a is the expected time between successive requests for the object, u is the expected time between successive updates of the object, p is the probability that the object will be accessed between successive updates to the object, and s is the size of the object.
Where the system further has one or more level 2 nodes coupled to one or more of the level 1 nodes, the cache replacement policy is preferably designed to minimize resources on at least one level 2 node. Here, the cache replacement policy can estimate the desirability of caching an object from the expected number of hits to the object per unit time if it is cached multiplied by the expected processing time on one or more of the level 2 nodes to fetch or calculate the object divided by the size of the object. The cache replacement policy preferably estimates the desirability of caching the object by calculating or estimating the quantity (t/axe2x88x92t*p/u)/s, where a is the expected time between successive requests for the object, t is the expected processing time on one or more of the level 2 nodes to fetch or calculate the object, u is the expected time between successive updates of the object, p is the probability that the object will be accessed between successive updates to the object, and s is the size of the object.
Where the system further has one or. more level 2 nodes and one or more networks located between the one or more level 1 nodes and the one or more level 2 nodes, the cache replacement policy is preferably designed to minimize traffic on one or more of the networks. Here, the cache replacement policy can estimate the desirability of caching an object from the expected number of hits to the object per unit time if the object is cached. Preferably, the cache replacement policy estimates the desirability of caching the object by calculating or estimating the quantity 1/axe2x88x92p/u, where a is the expected time between successive requests for the object, u is the expected time between successive updates of the object, and p is the probability that the object will be accessed between successive updates to the object.
It is preferable that the method of the present invention also include the step of dynamically varying the parts of the level 1 cache managed by at least one of the cache replacement policies.
Preferably, the method further includes the steps of determining one or more resource bottlenecks corresponding to one or more resources; and dynamically varying, in response to the determining step, the parts of the level 1 cache managed by at least one of the cache replacement policies. The dynamically varying step preferably includes the step of increasing, in response to the determining step, the part of the level 1 cache managed by a cache replacement policy designed to minimize utilization of the one or more resources.
The system can further have one or more level 2 nodes and one or more networks between the one or more level 1 nodes and the one or more level 2 nodes, wherein the one or more resources becoming a bottleneck contain at least one of: processing power of the level one node containing the level 1 cache, processing power of at least one of the level 2 nodes and bandwidth of at least one of the networks.
In a system adapted to receive requests for objects from one or more clients, the system having one or more level 1 nodes, each containing at least one level 1 cache, and having one or more level 2 nodes coupled to one or more of the level 1 nodes, a method for handling requests in the system includes the steps of: determining a level 1 node to be a bottleneck in the system; and sending, in response to the determining step, one or more requests to one or more level 2 nodes without first attempting to satisfy the one or more requests from a level 1 cache on the level 1 node.
In a system adapted to receive requests for objects from one or more clients, the system having a set of one or more level 1 nodes, each containing at least one level 1 cache, one or more level 2 nodes, and one or more networks between the one or more level 1 nodes and the one or more level 2 nodes, a method for handling requests in the system includes the steps of: determining at least one of the networks or at least one of the level 2 nodes to be a bottleneck in the system; and reducing, in response to the determining step, the number of requests sent to the one or more level 2 nodes without first attempting to satisfy the request from a level 1 cache.
Preferably, where the system further includes one or more level 2 nodes coupled to one or more level 1 nodes, the method further includes the step of: determining a level 1 node to be a bottleneck in the system; and sending, in response to the determining step, one or more requests to one or more level 2 nodes without first attempting to satisfy the one or more requests from a level 1 cache on the level 1 node.
Preferably, where the system further comprises one or more level 2 nodes and a network between the one or more level 1 nodes and the one or more level 2 nodes, the method further includes the steps of: determining at least one of the network or the level 2 nodes to be a bottleneck in the system; and reducing, in response to the determining step, the number of requests sent to one or more level 2 nodes without first attempting to satisfy the request from a level 1 cache.
Finally, the method of the present invention preferably includes the steps of determining, in response to the object not being found in the at least one level 1 cache, whether the requested object should be cached in any level 1 cache and satisfying, in response to the determination that the object should not be cached in any level 1 cache, the request in an optimized fashion. The satisfying step preferably includes the step of returning a response to the client from a level 2 node through at least one of the one or more level 1 nodes, bypassing the at least one level 1 cache or the step of returning a response to the client from a level 2 node, bypassing at least one of the one or more level 1 nodes.